package com.leetcode.双周赛.第45场;

/**
 * @author: xiaomi
 * @date: 2021/2/6
 * @description:    5658. 任意子数组和的绝对值的最大值
 * https://leetcode-cn.com/contest/biweekly-contest-45/problems/maximum-absolute-sum-of-any-subarray/
 * 子数组的问题还是挺适合用dp的，而且特征方程可能是：以i为底的子数组相关
 */
public class B_5658_任意子数组和的绝对值的最大值 {

    static B_5658_任意子数组和的绝对值的最大值 action =new B_5658_任意子数组和的绝对值的最大值();

    public static void main(String[] args) {
        test1();
    }

    static void test1(){
        int[] nums = new int[]{2, -5, 1, -4, 3, -2};
        int res = action.maxAbsoluteSumByDPLessMemory(nums);
        System.out.println("res = " + res);
    }

    /**
     * 这个应该要用 DP 的，但是目前只会 force
     * --
     * 卧槽，force 居然超时了！
     * @param nums
     * @return
     */
    public int maxAbsoluteSum(int[] nums) {
        int len = nums.length;
        int res = Integer.MIN_VALUE;
        int partSum = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                partSum += nums[j];
                res = Math.max(res, Math.abs(partSum));
            }
            partSum=0;
        }
        return res;
    }

    /**
     * 没想到这道题堆内存都还有限制
     * 那么就再内存上再优化一下吧！
     * @param nums
     * @return
     */
    public int maxAbsoluteSumByDP(int[] nums) {
        int len = nums.length;
        int[][] dp= new int[len][len];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            dp[i][i] = nums[i];
            res=Math.max(res,dp[i][i]>=0?dp[i][i]:-dp[i][i]);
            for (int j = i+1; j < len; j++) {
                dp[i][j] =dp[i][j-1] +nums[j];
                res=Math.max(res,dp[i][j]>=0?dp[i][j]:-dp[i][j]);
            }
        }
        return res;
    }

    /**
     * 卧槽居然超时了。
     * n^2 就超时？
     * @param nums
     * @return
     */
    public int maxAbsoluteSumByDPLessMemory(int[] nums) {
        int len = nums.length;
        int tempSum=0;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            tempSum = nums[i];
            res=Math.max(res,tempSum>=0?tempSum:-tempSum);
            for (int j = i+1; j < len; j++) {
                tempSum =tempSum +nums[j];
                res=Math.max(res,tempSum>=0?tempSum:-tempSum);
            }
        }
        return res;
    }

    /**
     * 这样也超时了，看了必须要一个 O(n) 的算法了。
     * @param nums
     * @return
     */
    public int maxAbsoluteSumByPrefixSum(int[] nums) {
        int len = nums.length;
        int tempSum=0;
        int max = nums[0];
        int min = nums[0];
        int[] prefixArr = new int[len];
        prefixArr[0]=nums[0];
        for (int i = 1; i < len; i++) {
            max = Math.max(max,nums[i]);
            min = Math.min(min,nums[i]);
            prefixArr[i]=prefixArr[i-1]+nums[i];
            max = Math.max(max,prefixArr[i]);
            min = Math.min(min,prefixArr[i]);
        }
        int interval=2;
        while (interval<len){
            int endIndex=len-interval;
            for (int i = 0; i < endIndex; i++) {
                int tempValue=prefixArr[i+interval]-prefixArr[i];
                max=Math.max(max, tempValue);
                min=Math.max(min, tempValue);
            }
            interval++;
        }

        return Math.max(Math.abs(max),Math.abs(min));
    }

    /**
     * 动态规划！
     * @param nums
     * @return
     */
    public int maxAbsoluteSumByReadDP(int[] nums){
        int len = nums.length;
        int[] dpMax = new int[len];
        dpMax[0]=nums[0];
        int max=dpMax[0];
        int[] dpMin = new int[len];
        dpMin[0]=nums[0];
        int min=dpMin[0];
        for (int i = 1; i < len; i++) {

            dpMax[i]=Math.max(nums[i],nums[i]+dpMax[i-1]);
            max=Math.max(dpMax[i],max);

            dpMin[i]=Math.min(nums[i],nums[i]+dpMin[i-1]);
            min=Math.min(dpMin[i],min);
        }
        return Math.max(Math.abs(max),Math.abs(min));
    }
}
